15.9 KB · ⇊ 10 parts · ⤓ Micron 15.9 KB · ⤓ HTML 77.8 KB

top

In mathematics, a polynomial decomposition expresses a polynomial f as the functional composition g ∘ ∘ h {\displaystyle g\circ h} of polynomials g and h, where g and h have degree greater than 1; it is an algebraic functional decomposition. Algorithms are known for decomposing univariate polynomials in polynomial time.

Polynomials which are decomposable in this way are composite polynomials; those which are not are indecomposable polynomials or sometimes prime polynomialscite-ref-ritt-1-0[1] (not to be confused with irreducible polynomials, which cannot be factored into products of polynomials). The degree of a composite polynomial is always a composite number, the product of the degrees of the composed polynomials.

The rest of this article discusses only univariate polynomials; algorithms also exist for multivariate polynomials of arbitrary degree.cite-ref-2[2]cite-ref-3[3]cite-ref-4[4]

• Examples

• Uniqueness

• Applications

• Algorithms

• Notes

• References

In the simplest case, one of the polynomials is a monomial. For example,

f ( x ) = x 6 − − 3 x 3 + 1 {\displaystyle f(x)=x^{6}-3x^{3}+1}

decomposes into g ∘ ∘ h {\displaystyle g\circ h} , where

g ( x ) = x 2 − − 3 x + 1 and h ( x ) = x 3 {\displaystyle g(x)=x^{2}-3x+1{\text{ and }}h(x)=x^{3}}

since

f ( x ) = ( g ∘ ∘ h ) ( x ) = g ( h ( x ) ) = g ( x 3 ) = ( x 3 ) 2 − − 3 ( x 3 ) + 1 , {\displaystyle f(x)=(g\circ h)(x)=g(h(x))=g(x^{3})=(x^{3})^{2}-3(x^{3})+1,}

using the ring operator symbol ∘ {\displaystyle \circ } to denote function composition. We write that as

x 6 − − 3 x 3 + 1 = ( x 2 − − 3 x + 1 ) ∘ ∘ ( x 3 ) {\displaystyle x^{6}-3x^{3}+1=(x^{2}-3x+1)\circ (x^{3})}

treating the polynomials implicitly as functions of x {\displaystyle x} .

Less trivially,

x 6 − − 6 x 5 + 21 x 4 − − 44 x 3 + 68 x 2 − − 64 x + 41 = ( x 3 + 9 x 2 + 32 x + 41 ) ∘ ∘ ( x 2 − − 2 x ) . {\displaystyle {\begin{aligned}&x^{6}-6x^{5}+21x^{4}-44x^{3}+68x^{2}-64x+41\\={}&(x^{3}+9x^{2}+32x+41)\circ (x^{2}-2x).\end{aligned}}}

A polynomial may have distinct decompositions into indecomposable polynomials where f = g 1 ∘ ∘ g 2 ∘ ∘ ⋯ ⋯ ∘ ∘ g m = h 1 ∘ ∘ h 2 ∘ ∘ ⋯ ⋯ ∘ ∘ h n {\displaystyle f=g_{1}\circ g_{2}\circ \cdots \circ g_{m}=h_{1}\circ h_{2}\circ \cdots \circ h_{n}} where g i ≠ ≠ h i {\displaystyle g_{i}\neq h_{i}} for some i {\displaystyle i} . The restriction in the definition to polynomials of degree greater than one excludes the infinitely many decompositions possible with linear polynomials.

Joseph Ritt proved that m = n {\displaystyle m=n} , and the degrees of the components are the same, but possibly in different order; this is Ritt's polynomial decomposition theorem.cite-ref-ritt-1-1[1]cite-ref-5[5] For example, x 2 ∘ ∘ x 3 = x 3 ∘ ∘ x 2 {\displaystyle x^{2}\circ x^{3}=x^{3}\circ x^{2}} . In fact, only three kinds of position swap are possible: between monomials; between Chebyshev polynomials T i ( x ) {\displaystyle T_{i}(x)} ; and between ( x k u ( x ) p , x p ) ↔ ↔ ( x p , x k u ( x p ) ) {\displaystyle \left(x^{k}\,u\left(x\right)^{p},x^{p}\right)\leftrightarrow \left(x^{p},x^{k}\,u\left(x^{p}\right)\right)} — summarized as "Every polynomial can be written as a composition of indecomposables, uniquely up to permutations and units."cite-ref-6[6] For example:

x 14 ( x 98 + 1 ) 2 = ( x ( x 7 + 1 ) 2 ) ∘ ∘ ( x 7 ) ∘ ∘ ( x 2 ) = ( x 2 ) ∘ ∘ ( x ( x 14 + 1 ) ) ∘ ∘ ( x 7 ) {\displaystyle x^{14}\,\left(x^{98}+1\right)^{2}=\left(x\,\left(x^{7}+1\right)^{2}\right)\circ \left(x^{7}\right)\circ \left(x^{2}\right)=\left(x^{2}\right)\circ \left(x\,\left(x^{14}+1\right)\right)\circ \left(x^{7}\right)}

T 2 ( x ) ∘ ∘ T 3 ( x ) = T 3 ( x ) ∘ ∘ T 2 ( x ) = 32 x 6 − − 48 x 4 + 18 x 2 − − 1 {\displaystyle T_{2}(x)\circ T_{3}(x)=T_{3}(x)\circ T_{2}(x)=32\,x^{6}-48\,x^{4}+18\,x^{2}-1}

A polynomial decomposition may enable more efficient evaluation of a polynomial. For example,

x 8 + 4 x 7 + 10 x 6 + 16 x 5 + 19 x 4 + 16 x 3 + 10 x 2 + 4 x − − 1 = ( x 2 − − 2 ) ∘ ∘ ( x 2 ) ∘ ∘ ( x 2 + x + 1 ) {\displaystyle {\begin{aligned}&x^{8}+4x^{7}+10x^{6}+16x^{5}+19x^{4}+16x^{3}+10x^{2}+4x-1\\={}&\left(x^{2}-2\right)\circ \left(x^{2}\right)\circ \left(x^{2}+x+1\right)\end{aligned}}}

can be calculated with 3 multiplications and 3 additions using the decomposition, while Horner's method would require 7 multiplications and 8 additions.

A polynomial decomposition enables calculation of symbolic roots using radicals, even for some irreducible polynomials. This technique is used in many computer algebra systems.cite-ref-7[7] For example, using the decomposition

x 6 − − 6 x 5 + 15 x 4 − − 20 x 3 + 15 x 2 − − 6 x − − 1 = ( x 3 − − 2 ) ∘ ∘ ( x 2 − − 2 x + 1 ) , {\displaystyle {\begin{aligned}&x^{6}-6x^{5}+15x^{4}-20x^{3}+15x^{2}-6x-1\\={}&\left(x^{3}-2\right)\circ \left(x^{2}-2x+1\right),\end{aligned}}}

the roots of this irreducible polynomial can be calculated ascite-ref-indep-8-0[8]

1 ± ± 2 1 / 6 , 1 ± ± − − 1 ± ± 3 i 2 1 / 3 . {\displaystyle 1\pm 2^{1/6},1\pm {\frac {\sqrt {-1\pm {\sqrt {3}}i}}{2^{1/3}}}.}

Even in the case of quartic polynomials, where there is an explicit formula for the roots, solving using the decomposition often gives a simpler form. For example, the decomposition

x 4 − − 8 x 3 + 18 x 2 − − 8 x + 2 = ( x 2 + 1 ) ∘ ∘ ( x 2 − − 4 x + 1 ) {\displaystyle {\begin{aligned}&x^{4}-8x^{3}+18x^{2}-8x+2\\={}&(x^{2}+1)\circ (x^{2}-4x+1)\end{aligned}}}

gives the rootscite-ref-indep-8-1[8]

2 ± ± 3 ± ± i {\displaystyle 2\pm {\sqrt {3\pm i}}}

but straightforward application of the quartic formula gives equivalent results but in a form that is difficult to simplify and difficult to understand; one of the four roots is:

2 − − 9 ( 8 10 i 3 3 / 2 + 72 ) 2 / 3 + 36 ( 8 10 i 3 3 / 2 + 72 ) 1 / 3 + 156 ( 8 10 i 3 3 / 2 + 72 ) 1 / 3 6 − − − − ( 8 10 i 3 3 / 2 + 72 ) 1 / 3 − − 52 3 ( 8 10 i 3 3 / 2 + 72 ) 1 / 3 + 8 2 . {\displaystyle 2-{\frac {\sqrt {{9\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{2/3}+36\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}+156} \over {\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}}{6}}-{{\sqrt {-\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}-{{52} \over {3\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}+8}} \over 2}.}

The first algorithm for polynomial decomposition was published in 1985,cite-ref-bz-9-0[9] though it had been discovered in 1976,cite-ref-z-10-0[10] and implemented in the Macsyma/Maxima computer algebra system.cite-ref-11[11] That algorithm takes exponential time in worst case, but works independently of the characteristic of the underlying field.

A 1989 algorithm runs in polynomial time but with restrictions on the characteristic.cite-ref-kz-12-0[12]

A 2014 algorithm calculates a decomposition in polynomial time and without restrictions on the characteristic.cite-ref-13[13]

cite-note-ritt-11. ↑ J.F. Ritt, "Prime and Composite Polynomials", Transactions of the American Mathematical Society 23:1:51–66 (January, 1922) doi:10.2307/1988911 JSTOR 1988911

cite-note-22. ↑ Jean-Charles Faugère, Ludovic Perret, "An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography", Journal of Symbolic Computation, 44:1676-1689 (2009), doi:10.1016/j.jsc.2008.02.005

cite-note-33. ↑ citerefzhaofenggao2012Zhao, Shangwei; Feng, Ruyong; Gao, Xiao-Shan (2012-04-01). "On functional decomposition of multivariate polynomials with differentiation and homogenization". Journal of Systems Science and Complexity. 25 (2): 329–347. doi:10.1007/s11424-012-1144-8. ISSN 1559-7067.

cite-note-44. ↑ citerefvon-zur-gathenziegler2015von zur Gathen, Joachim; Ziegler, Konstantin (2015), Gutierrez, Jaime; Schicho, Josef; Weimann, Martin (eds.), "Survey on Counting Special Types of Polynomials", Computer Algebra and Polynomials: Applications of Algebra and Number Theory, Cham: Springer International Publishing, pp. 50–75, doi:10.1007/978-3-319-15081-9_3, ISBN 978-3-319-15081-9, retrieved 2025-07-14

cite-note-55. ↑ Capi Corrales-Rodrigáñez, "A note on Ritt's theorem on decomposition of polynomials", Journal of Pure and Applied Algebra 68:3:293–296 (6 December 1990) doi:10.1016/0022-4049(90)90086-W

cite-note-66. ↑ citerefmedvedevscanlon2018Medvedev, Alice; Scanlon, Thomas (August 31, 2018). "Ritt's Theorem and refinements" (PDF). DART XI (Differential Algebra and Related Topics). University of Leeds.

cite-note-77. ↑ The examples below were calculated using Maxima.

cite-note-indep-88. ↑ Where each ± is taken independently.

cite-note-bz-99. ↑ citerefdavid-r-barton-richard-zippel1985David R. Barton, Richard Zippel (1985). "Polynomial Decomposition Algorithms". Journal of Symbolic Computation. 1 (2): 159–168. doi:10.1016/S0747-7171(85)80012-2.

cite-note-z-1010. ↑ Richard Zippel, Functional Decomposition, 1996.

cite-note-1111. ↑ See the polydecomp function.

cite-note-kz-1212. ↑ citerefkozenlandau1989Kozen, Dexter; Landau, Susan (1989). "Polynomial Decomposition Algorithms". Journal of Symbolic Computation. 7 (5): 445–456. CiteSeerX 10.1.1.416.6491. doi:10.1016/S0747-7171(89)80027-6.

cite-note-1313. ↑ citerefraoul-blankertz2014Raoul Blankertz (2014). "A polynomial time algorithm for computing all minimal decompositions of a polynomial" (PDF). ACM Communications in Computer Algebra. 48 (187): 1. Archived 2015-09-24 at the Wayback Machine

• citerefjoel-s-cohen2003Joel S. Cohen (2003). "Chapter 5. Polynomial Decomposition". Computer Algebra and Symbolic Computation: Mathematical Methods. ISBN 1-56881-159-4.